#pragma once
//作为map和set底层存在的红黑树
enum col
{
	Red,
	Black,
};
template<class T>
struct RBTreeNode
{
	T _data;
	RBTreeNode<T>* _left;
	RBTreeNode<T>* _right;
	RBTreeNode<T>* _parent;
	col _col;
	RBTreeNode(const T& data)
		:_data(data)
		, _left(nullptr)
		, _right(nullptr)
		, _parent(nullptr)
		, _col(Red)

	{}
};

//迭代器
template<class T>
struct _RBTreeiterator
{
	typedef RBTreeNode<T> Node;
	typedef _RBTreeiterator<T> Self;
	Node* _node;
	_RBTreeiterator(Node* node)
		:_node(node)
	{}
	T& operator*()
	{
		return _node->_data;
	}
	T* operator->()
	{
		return &_node->_data;
	}
	Self& operator++()
	{
		//首先需要找到最左节点
		if (_node->_right)
		{
			Node* min = _node->_right;
			while (min->_left)
			{
				min = min->_left;
			}
			_node = min;
		}
		else
		{
			Node* cur = _node;
			Node* parent = cur->_parent;
			
			while (parent && cur ==parent->_right)
			{
				cur = cur->_parent;
				parent = parent->_parent;
			}
			_node = parent;
		}
		return *this;
	}
	bool operator!=(const Self& s)
	{
		return _node != s._node;
	}

};



//有三个参数，class Value(用于Insert(const KeyValue)) class Value(存map或者set的数据类型)  class KeyOfValue
template<class K, class T,class KeyofT>
class RBTree
{
public:
	typedef RBTreeNode<T> Node;
	typedef _RBTreeiterator<T> iterator;
public:

	iterator begin()
	{
		Node* left = _root;
		while (left && left->_left)
		{
			left = left->_left;
		}
		return iterator(left);
	}

	iterator end()
	{
		return iterator(nullptr);
	}

	bool Insert(const T& data)
	{
		if (_root == nullptr)
		{
			_root = new Node(data);
			_root->_col = Black;
			return true;
		}
		//寻找位置插入kv
		KeyofT keyoft;
		Node* cur = _root;
		Node* parent = nullptr;
		while (cur)
		{
			//小于根节点的值，往左走
			//对于map和set的底层而言，不能直接用first去比较
			//因为不知道传过来的是pair还是Value，所以需要写一个仿函数
			//因为operator<()已经被重载过了
			//对于pair需要比价第一个参数，对于set，比较值即可
			if (keyoft(cur->_data) > keyoft(data))
			{
				parent = cur;
				cur = cur->_left;
			}
			else if (keyoft(cur->_data) < keyoft(data))
			{
				parent = cur;
				cur = cur->_right;
			}
			else
			{
				//有相等的值，直接返回false并退出
				return false;
			}
		}
		//当循环退出的时候，cur为空，找到了值
		cur = new Node(data);
		cur->_col = Red;//违反了规则3，需要进行调整
		if (keyoft(parent->_data) > keyoft(data))
		{
			//链接在左边
			parent->_left = cur;
			cur->_parent = parent;
		}
		else
		{
			parent->_right = cur;
			cur->_parent = parent;
		}
		//新的cur的颜色为RED，判断parent的颜色是否是红色
		//如果是红色的话，就需要调整
		//如果是黑色的话，就不需要调整
		while (parent && parent->_col == Red)
		{
			Node* grandfather = parent->_parent;
			//这是parent在grandparent的左边的情况
			if (grandfather->_left == parent)
			{
				Node* uncle = grandfather->_right;
				//uncle存在，并且为红色
				//情况一:把p,u的颜色置黑色，g的颜色置为红色
				if (uncle && uncle->_col == Red)
				{
					uncle->_col = parent->_col = Black;
					grandfather->_col = Red;
					//继续向上迭代，直到根
					cur = grandfather;
					parent = cur->_parent;
				}
				else //情况二三
				{
					//情况2
					if (cur == parent->_left)
					{
						//进行右旋
						RotateR(grandfather);
						//右旋之后，把g置为红色，p置为黑色
						grandfather->_col = Red;
						parent->_col = Black;
					}
					//情况三  成折线型
					else
					{
						RotateL(parent); //cur替代了parent的位置
						RotateR(grandfather);//cur成了最上面那个节点
						//把cur置为黑色，g置红色，p不用管
						cur->_col = Black;
						grandfather->_col = Red;
					}
					//在情况二三执行完成之后，直接跳出循环即可
					break;
				}

			}
			//这是parent在grandparent的右边的情况
			else
			{
				Node* uncle = grandfather->_left;
				//跟在右边一样，分为三种情况
				//情况一
				if (uncle && uncle->_col == Red)
				{
					uncle->_col = parent->_col = Black;
					grandfather->_col = Red;

					//继续向上迭代，直到根
					cur = grandfather;
					parent = cur->_parent;
				}
				else
				{
					//情况2
					if (cur == parent->_right)
					{
						//进行左旋
						RotateL(grandfather);
						//左旋之后，把g置为红色，p置为黑色
						grandfather->_col = Red;
						parent->_col = Black;
					}
					//情况三  成折线型
					else
					{
						RotateR(parent); //cur替代了parent的位置
						RotateL(grandfather);//cur成了最上面那个节点
						//把cur置为黑色，g置红色，p不用管
						cur->_col = Black;
						grandfather->_col = Red;
					}
					//在情况二三执行完成之后，直接跳出循环即可
					break;
				}
			}
		}

		//无论怎么样，把_root的颜色变成黑色
		_root->_col = Black;
		return true;
	}

	//左旋
	void RotateL(Node* parent)
	{
		Node* sub = parent->_right;
		Node* subL = sub->_left;

		parent->_right = subL;
		if (subL)
			subL->_parent = parent;
		Node* ppNode = parent->_parent;
		if (ppNode)
		{
			if (ppNode->_left == parent)
			{
				ppNode->_left = sub;
			}
			else
			{
				ppNode->_right = sub;
			}
			sub->_parent = ppNode;
		}
		else
		{
			_root = sub;
			sub->_parent = nullptr;
		}

		sub->_left = parent;
		parent->_parent = sub;
	}

	//右旋
	void RotateR(Node* parent)
	{
		Node* sub = parent->_left;
		Node* subR = sub->_right;

		parent->_left = subR;
		if (subR)
			subR->_parent = parent;
		Node* ppNode = parent->_parent;
		if (ppNode)
		{
			if (ppNode->_left == parent)
			{
				ppNode->_left = sub;
			}
			else
			{
				ppNode->_right = sub;
			}
			sub->_parent = ppNode;
		}
		else
		{
			_root = sub;
			_root->_parent = nullptr;
		}

		sub->_right = parent;
		parent->_parent = sub;

	}
	//void Inorder()
	//{
	//	_Inorder(_root);
	//}
	//void _Inorder(Node* root)
	//{
	//	if (root == nullptr)
	//	{
	//		return;
	//	}
	//	_Inorder(root->_left);
	//	cout << root->_kv.first << ":" << root->_kv.second << endl;
	//	_Inorder(root->_right);
	//}

	//bool _isBalance()
	//{
	//	return isBalance(_root);
	//}
	//bool isBalance(Node* root)
	//{
	//	if (root == nullptr)
	//	{
	//		return true;
	//	}
	//	if (root->_col != Black)
	//	{
	//		return false;
	//	}
	//	int n = 0; //用来记录最左路径的黑色节点的个数
	//	//因为红黑树规定，每条路径的黑色节点个数是相等的
	//	Node* cur = root;
	//	while (cur)
	//	{
	//		if (cur->_col == Black)
	//		{
	//			++n;
	//		}
	//		cur = cur->_left;
	//	}
	//	return Check(root, 0, n);
	//}
	//bool Check(Node* root, int x, int numofBalck)
	//{
	//	//寻找是否有两个连续的红色
	//	if (root == nullptr)
	//	{
	//		if (x != numofBalck)
	//		{
	//			return false;
	//		}
	//		return true;
	//	}
	//	if (root->_col == Black)
	//	{
	//		++x;
	//	}
	//	if (root->_col == Red && root->_parent->_col == Red)
	//	{
	//		cout << "违反规则:出现连续的红色节点" << endl;
	//		return false;
	//	}

	//	return Check(root->_left, x, numofBalck)
	//		&& Check(root->_right, x, numofBalck);
	//}


private:
	Node* _root = nullptr;
};






namespace myRBTree
{
#pragma once

	enum col
	{
		Red,
		Black,
	};
	template<class K, class V>
	struct RBTreeNode
	{
		pair<K, V> _kv;
		RBTreeNode<K, V>* _left;
		RBTreeNode<K, V>* _right;
		RBTreeNode<K, V>* _parent;
		col _col;
		RBTreeNode(const pair<K, V>& kv)
			:_kv(kv)
			, _left(nullptr)
			, _right(nullptr)
			, _parent(nullptr)
			, _col(Red)

		{}
	};

	template<class K, class V>
	class RBTree
	{
		typedef RBTreeNode<K, V> Node;
	public:
		bool Insert(const pair<K, V>& kv)
		{
			if (_root == nullptr)
			{
				_root = new Node(kv);
				_root->_col = Black;
				return true;
			}
			//寻找位置插入kv
			Node* cur = _root;
			Node* parent = nullptr;
			while (cur)
			{
				//小于根节点的值，往左走
				if (cur->_kv.first > kv.first)
				{
					parent = cur;
					cur = cur->_left;
				}
				else if (cur->_kv.first < kv.first)
				{
					parent = cur;
					cur = cur->_right;
				}
				else
				{
					//有相等的值，直接返回false并退出
					return false;
				}
			}
			//当循环退出的时候，cur为空，找到了值
			cur = new Node(kv);
			cur->_col = Red;//违反了规则3，需要进行调整
			if (parent->_kv.first > kv.first)
			{
				//链接在左边
				parent->_left = cur;
				cur->_parent = parent;
			}
			else
			{
				parent->_right = cur;
				cur->_parent = parent;
			}
			//新的cur的颜色为RED，判断parent的颜色是否是红色
			//如果是红色的话，就需要调整
			//如果是黑色的话，就不需要调整
			while (parent && parent->_col == Red)
			{
				Node* grandfather = parent->_parent;
				//这是parent在grandparent的左边的情况
				if (grandfather->_left == parent)
				{
					Node* uncle = grandfather->_right;
					//uncle存在，并且为红色
					//情况一:把p,u的颜色置黑色，g的颜色置为红色
					if (uncle && uncle->_col == Red)
					{
						uncle->_col = parent->_col = Black;
						grandfather->_col = Red;
						//继续向上迭代，直到根
						cur = grandfather;
						parent = cur->_parent;
					}
					else //情况二三
					{
						//情况2
						if (cur == parent->_left)
						{
							//进行右旋
							RotateR(grandfather);
							//右旋之后，把g置为红色，p置为黑色
							grandfather->_col = Red;
							parent->_col = Black;
						}
						//情况三  成折线型
						else
						{
							RotateL(parent); //cur替代了parent的位置
							RotateR(grandfather);//cur成了最上面那个节点
							//把cur置为黑色，g置红色，p不用管
							cur->_col = Black;
							grandfather->_col = Red;
						}
						//在情况二三执行完成之后，直接跳出循环即可
						break;
					}

				}
				//这是parent在grandparent的右边的情况
				else
				{
					Node* uncle = grandfather->_left;
					//跟在右边一样，分为三种情况
					//情况一
					if (uncle && uncle->_col == Red)
					{
						uncle->_col = parent->_col = Black;
						grandfather->_col = Red;

						//继续向上迭代，直到根
						cur = grandfather;
						parent = cur->_parent;
					}
					else
					{
						//情况2
						if (cur == parent->_right)
						{
							//进行左旋
							RotateL(grandfather);
							//左旋之后，把g置为红色，p置为黑色
							grandfather->_col = Red;
							parent->_col = Black;
						}
						//情况三  成折线型
						else
						{
							RotateR(parent); //cur替代了parent的位置
							RotateL(grandfather);//cur成了最上面那个节点
							//把cur置为黑色，g置红色，p不用管
							cur->_col = Black;
							grandfather->_col = Red;
						}
						//在情况二三执行完成之后，直接跳出循环即可
						break;
					}
				}
			}

			//无论怎么样，把_root的颜色变成黑色
			_root->_col = Black;
			return true;
		}

		//左旋
		void RotateL(Node* parent)
		{
			Node* sub = parent->_right;
			Node* subL = sub->_left;

			parent->_right = subL;
			if (subL)
				subL->_parent = parent;
			Node* ppNode = parent->_parent;
			if (ppNode)
			{
				if (ppNode->_left == parent)
				{
					ppNode->_left = sub;
				}
				else
				{
					ppNode->_right = sub;
				}
				sub->_parent = ppNode;
			}
			else
			{
				_root = sub;
				sub->_parent = nullptr;
			}

			sub->_left = parent;
			parent->_parent = sub;
		}

		//右旋
		void RotateR(Node* parent)
		{
			Node* sub = parent->_left;
			Node* subR = sub->_right;

			parent->_left = subR;
			if (subR)
				subR->_parent = parent;
			Node* ppNode = parent->_parent;
			if (ppNode)
			{
				if (ppNode->_left == parent)
				{
					ppNode->_left = sub;
				}
				else
				{
					ppNode->_right = sub;
				}
				sub->_parent = ppNode;
			}
			else
			{
				_root = sub;
				_root->_parent = nullptr;
			}

			sub->_right = parent;
			parent->_parent = sub;

		}
		void Inorder()
		{
			_Inorder(_root);
		}
		void _Inorder(Node* root)
		{
			if (root == nullptr)
			{
				return;
			}
			_Inorder(root->_left);
			cout << root->_kv.first << ":" << root->_kv.second << endl;
			_Inorder(root->_right);
		}

		bool _isBalance()
		{
			return isBalance(_root);
		}
		bool isBalance(Node* root)
		{
			if (root == nullptr)
			{
				return true;
			}
			if (root->_col != Black)
			{
				return false;
			}
			int n = 0; //用来记录最左路径的黑色节点的个数
			//因为红黑树规定，每条路径的黑色节点个数是相等的
			Node* cur = root;
			while (cur)
			{
				if (cur->_col == Black)
				{
					++n;
				}
				cur = cur->_left;
			}
			return Check(root, 0, n);
		}
		bool Check(Node* root, int x, int numofBalck)
		{
			//寻找是否有两个连续的红色
			if (root == nullptr)
			{
				if (x != numofBalck)
				{
					return false;
				}
				return true;
			}
			if (root->_col == Black)
			{
				++x;
			}
			if (root->_col == Red && root->_parent->_col == Red)
			{
				cout << "违反规则:出现连续的红色节点" << endl;
				return false;
			}

			return Check(root->_left, x, numofBalck)
				&& Check(root->_right, x, numofBalck);
		}


	private:
		Node* _root = nullptr;
	};

	void testRBTree()
	{
		//int a[] = { 8, 3, 1, 10, 6, 4, 7, 14, 13 };
		//int a[] = { 16,3,7,11,9,26,18,14,15 };
		int a[] = { 4,2,6,1,3,5,15,7,16,14 };
		RBTree<int, int> t;
		for (auto& e : a)
		{
			t.Insert(make_pair(e, e));
		}
		t.Inorder();
		cout << t._isBalance() << endl;
	}



}

